public class MergeSort {
    /**
     * 归并排序：
     *  先递归分解 再回归合并*/
    public static void mergeSort(int[] array) {
        merge(array,0,array.length-1);
    }
    private static void merge(int[] array, int left, int right) {
        if(left>=right) {
            return;
        }
        
        /**
         * 2024/2/26
         *  初次练习归并排序，不慎将 mid 的求法写为：mid = (right-left)/2
         *  这是非常低级的错误，望谨记
         *  */

        int mid = (right+left)/2;
        //递推分解
        merge(array,left,mid);
        merge(array,mid+1,right);
        //回归排序
        mergeDemo(array,left,right,mid);
    }
    private static void mergeDemo(int[] array, int left, int right,int mid) {
        //和以前做过的 合并两个有序链表相似
        //定义临时数组用于排序 定义计数器k用于维护数组
        int[] tmpArray = new int[right-left+1];
        int k = 0;

        int rightFront = mid+1;
        int record = left;
        while(left<=mid && rightFront<=right) {
            if(array[left]<array[rightFront]) {
                tmpArray[k++] = array[left++];
            } else {
                tmpArray[k++] = array[rightFront++];
            }
        }
        while(left<=mid) {
            tmpArray[k++] = array[left++];
        }
        while(rightFront<=right) {
            tmpArray[k++] = array[rightFront++];
        }
        //将临时数组中已排序的元素同步到array数组中
        for(int i = 0; i < tmpArray.length; i++) {
            array[i+record] = tmpArray[i];
        }
    }
}
